package FINAL.find_monitors;

import FINAL.CONSTANT;
import FINAL.Read_file_to_matrix;

public class Calculator_Incoming_edges {
	public static void main(String[] args) {
		int[] list = incoming_edges(Read_file_to_matrix.read_file_to_matrix());
		int[] kq = sort_incoming_edges(list);
		for (int i = 0; i < kq.length; i++) {
			System.out.println(kq[i] + " ");
		}
	}

	/**
	 * 
	 * @param k
	 *            số lượng node giám sát cần tìm
	 * @return mảng id của k node giám sát
	 */
	public static int[] IN(int k) {
		int[] kq = new int[k];
		int[] list = incoming_edges(Read_file_to_matrix.read_file_to_matrix());
		// hàm read_file_to_matrix thực hiện tạo ma trận từ file dữ liệu
		int[] in = sort_incoming_edges(list);

		for (int i = 0; i < kq.length; i++) {
			kq[i] = in[i];
		}
		return kq;
	}

	/**
	 * 
	 * @param list
	 *            đưa vào ma trận 2 chiều biễu diễn đồ thị
	 * @return trả về mảng chứa số cạnh đến của tất cả các đỉnh
	 */
	public static int[] incoming_edges(int[][] list) {
		int incoming[] = new int[7500];
		for (int i = 0; i < 7500; i++) {
			for (int j = 0; j < 7500; j++) {
				if (list[i][j] == 1) {
					incoming[j]++;
				}
			}
		}
		return incoming;
	}

	/**
	 * 
	 * @param incoming
	 *            đưa vào mảng lưu số cạnh đến của tất cả các node
	 * @return mảng chưa tất cả các node theo thứ tự có số cạnh đến giảm dần
	 */
	public static int[] sort_incoming_edges(int[] incoming) {
		int[] ketqua = new int[CONSTANT.SIZE];
		for (int i = 0; i < CONSTANT.SIZE; i++) {
			ketqua[i] = i;
		}

		// ///////////////////sort
		for (int i = 0; i < CONSTANT.SIZE; i++) {
			for (int j = i + 1; j < CONSTANT.SIZE; j++) {
				if (incoming[i] < incoming[j]) {
					// sort incoming array
					int tmp = incoming[i];
					incoming[i] = incoming[j];
					incoming[j] = tmp;
					// sort ketqua
					int tmp2 = ketqua[i];
					ketqua[i] = ketqua[j];
					ketqua[j] = tmp2;
				}
			}
		}
		return ketqua;
	}
}
